package greedy_algorithm

import "algo/heap"

type char struct {
	data   byte
	Weight int
}

type HuffmanTreeNode struct {
	data        byte
	Weight      int
	Left, Right *HuffmanTreeNode
}

// Huffman 由于golang中没有办法显示的使用bit，因此此处仅处如何对不同字符进行编码,返回结果用二进制字符串表示
func Huffman(chars map[byte]int) *HuffmanTreeNode {
	h := heap.NewHeap[*HuffmanTreeNode](false, func(h1, h2 *HuffmanTreeNode) bool {
		if h1.Weight < h2.Weight {
			return true
		}
		return false
	})
	for k, v := range chars {
		h.Push(&HuffmanTreeNode{
			data:   k,
			Weight: v,
		})
	}

	for {
		huff := &HuffmanTreeNode{}
		left, ok1 := h.Pop()
		right, ok2 := h.Pop()
		if ok1 {
			huff.Left = left
			huff.Weight += left.Weight
		}

		if ok2 {
			huff.Right = right
			huff.Weight += right.Weight
		}
		if h.Empty() {
			return huff
		}
		h.Push(huff)
	}
}
